package com.banmao.algorithm.No501To700.No654;

public class Solution2 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {

        if(nums.length == 0) {
            return null;
        }

        TreeNode root = recrusive(nums, 0, nums.length);

        return root;

    }

    private TreeNode recrusive(int[] nums, int low, int hight) {

        int max = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = low; i < hight; i++) {
            if(nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
        }

        if(maxIndex == -1) {
            return null;
        }

        TreeNode node = new TreeNode(max);

        if(maxIndex > low) {
            TreeNode left = recrusive(nums, low, maxIndex);
            node.left = left;
        }
        if(maxIndex < hight) {
            TreeNode right = recrusive(nums, maxIndex + 1, hight);
            node.right = right;
        }
        return node;

    }

}
